The Diffie-Hellman key exchange protocol allows two parties, Alice and Bob, to agree on a secret key without having exchanged any secret information beforehand! The method is based in cyclic groups, so read up on that in the mathematical prerequisites.
The protocol itself is based on the group
One such prime $p$ can be found in [RFC 3526](https://www.rfc-editor.org/rfc/rfc3526#page-5) and is 4096 bits long.
Notice that since
The primes
Alice picks a random power between
Alice now computes
Alice | Bob | Eve | |
---|---|---|---|
known | known | known | |
known | known | known | |
known | known | known | |
known | unknown | unknown | |
unknown | known | unknown | |
known | known | known | |
known | known | known | |
known | known | unknown |
The security of the Diffie-Hellman protocol is defined according to certain mathematical problems.
In trying to break the Diffie-Hellman key exchange, the adversary Eve is in a way trying to solve the discrete logarithm problem. The function
The adversary $\textit{Eve}$ is given the generator $g$ as well as the order $q$ of the generated group $\langle g \rangle$ and is provided with the group element $g^x$ for some uniform, unknown, $x \leftarrow_R \mathbb{Z}_q$. Her goal is to find the value of $x$.
We say that the discrete logarithm problem is *hard relative to* $\langle g \rangle$ if no matter what Eve does, the probability that she can find $x$ is negligible, i.e.
$$\Pr_{x\leftarrow_R \mathbb{Z}_q}[\textit{Eve}(g, q, g^x) = x] \le \textit{negl}(\cdot)$$
It should be obvious that the computational difficulty of the discrete logarithm largely depends on the group itself and so not every group yields a secure Diffie-Hellman key exchange.
There are two additional problems which are similar to the discrete logarithm problem and are known to be related but not equivalent to the each other.
The adversary $\textit{Eve}$ is given the generator $g$ as well as the order $q$ of the generated group $\langle g \rangle$ and is provided with two group elements $g^a$ and $g^b$ for some uniform, unknown, $a,b \leftarrow_R \mathbb{Z}_q$. Her goal is to then find the value of $g^{ab}$.
We say that the computational diffie-hellman problem is *hard relative to* $\langle g \rangle$ if, no matter what Eve does, the probability that she can find $g^{ab}$ is negligible, i.e.
$$\Pr_{a,b \leftarrow_R \mathbb{Z}_q}[\textit{Eve}(g, q, g^a, g^b) = g^{ab}] \le \textit{negl}(\cdot)$$
The CDH problem is essentially an exact description of the Diffie-Hellman scenario. Eve can observe the communication between Alice and Bob and is thus able to obtain the values
The second problem is related to the CDH problem but the two problems are not known to be equivalent.
The adversary $\textit{Eve}$ knows the cyclic group $\mathbb{G}$, one of its generators $g$ and its order $q$. She is given two group elements $g^{\alpha}, g^{\beta}$ which are generated by $g$ for some uniform, unknown to Eve, powers $\alpha, \beta \leftarrow_R \mathbb{Z}_q$. Finally, Eve is either given a third such element $g^{\gamma}$ generated by some uniform unknown $\gamma \leftarrow_R \mathbb{Z}_q$ or she is given the element $g^{\alpha\beta}$. Eve's goal is to then determine if she has $g^{\alpha\beta}$ or $g^{\gamma}$.
We say that the DDH problem is *hard relative to* $\mathbb{G}$ if no matter what Eve does, the probability that she achieves her goal is negligible, i.e.
$$\left|\Pr[\textit{Eve}(\mathbb{G}, g, q, g^{\alpha}, g^{\beta}, g^{\gamma}) = 1] - \Pr[\textit{Eve}(\mathbb{G}, g, q, g^{\alpha}, g^{\beta}, g^{\alpha\beta}) = 1] \right| \le \textit{negl}(\cdot)$$
If the CDH problem is easy relative to some group, then so is the DDH problem.